package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ32 密码截取
 * @Date: created in 2024/12/29 星期日 15:20
 * @Modified By:
 */
public class HJ32_PasswordCapture {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            // 使用中心扩散法判断
            System.out.println(check(s));
            // 使用动态规划判断
            System.out.println(validLen(s));
        }
    }

    public static int check(String s) {
        int res = 0;
        for (int i = 1; i < s.length(); i++) {
            // ABA类型的判断
            int len1 = longest(s, i, i);
            // ABBA类型的判断
            int len2 = longest(s, i, i + 1);
            // 两种类型取最长的
            res = Math.max(res, Math.max(len1, len2));
        }
        return res;
    }

    // 使用中心扩散法判断是否为回文字符串
    public static int longest(String s, int l, int r) {
        // 回文字符串的判断, 实际上就是两个指针, 分别比较前进/后退的字母是否一样
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }

        return r - l - 1;
    }

    // 使用动态规划判断是否为回文字符串
    public static int validLen(String s) {
        //     A B B A
        //     0 1 2 3
        // A 0 T F F T
        // B 1   T T F
        // B 2     T F
        // A 3       T
        int len = s.length();
        // 状态：对比的两个字符索引起始和终止索引位置
        // dp 数组：字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串
        boolean[][] dp = new boolean[len][len];
        int res = 0;
        // base case l=r时单字母默认为回文子串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int r = 1; r < len; r++) {
            for (int l = 0; l < r; l++) {
                // 状态转移: 如果左右两字符相等, 同时[l+1...r-1]范围内的字符是回文子串,
                // 则 [l...r] 也是回文子串
                // r - l < 2 是处理ABBA, BB的时候要先设置dp位为true
                if (s.charAt(r) == s.charAt(l) && (r - l < 2 || dp[r - 1][l + 1])) {
                    dp[r][l] = true;
                    // 不断更新最大长度
                    res = Math.max(res, r - l + 1);
                }
            }
        }

        return res;
    }
}
